package main

import (
	"fmt"
	"math/rand"
)

// main
//
//	@Description: 双向链表
func main() {

	base := CreateBaseNode()
	AddFirst(base, -1)
	AddFirst(base, -2)
	AddFirst(base, -3)
	AddFirst(base, -4)
	AddLast(base, 1)
	AddLast(base, 2)
	AddLast(base, 3)
	AddLast(base, 4)
	PrintHeadToTail(base)
	fmt.Println()
	PrintTailToHead(base)
	fmt.Println()
	DeleteNode(base, 0)
	PrintHeadToTail(base)
}

type Node struct {
	Prev *Node // 前驱节点
	Ele  interface{}
	Next *Node // 后继节点
}

// AddFirst
//
//	@Description: 在头部添加节点
//	@param base
//	@param e
func AddFirst(base *Node, e interface{}) {
	if base == nil {
		base = CreateBaseNode()
	}
	head := GetHead(base)
	node := &Node{
		Ele: e,
	}
	head.Prev = node //head节点的前驱指向node节点
	node.Next = head //node节点的后继指向head节点
}

// CreateBaseNode
//
//	@Description: 创建一个空的双向链表
//	@return *Node
func CreateBaseNode() *Node {
	node := &Node{
		Ele: 0,
	}
	return node
}

// AddLast
//
//	@Description: 在尾部添加节点
//	@param base
//	@param e
func AddLast(base *Node, e interface{}) {
	if base == nil {
		base = CreateBaseNode()
	}
	tail := GetTail(base)
	node := &Node{
		Ele: e,
	}
	tail.Next = node //tail节点的后继指向node节点
	node.Prev = tail //node节点的前驱指向tail节点
}

// PrintHeadToTail
//
//	@Description: 从头打印到尾
//	@param n
func PrintHeadToTail(n *Node) {
	if n == nil {
		fmt.Println("空链表")
		return
	}
	head := GetHead(n)
	cur := head
	for cur != nil {
		fmt.Printf("Prev=%p | ptr=%p ele=%v | next=%p \n", cur.Prev, cur, cur.Ele, cur.Next)
		cur = cur.Next //当前节点向后移动一位
	}
}

// PrintTailToHead
//
//	@Description: 从尾打印到头
//	@param n
func PrintTailToHead(n *Node) {
	if n == nil {
		fmt.Println("空链表")
		return
	}
	tail := GetTail(n)
	cur := tail
	for cur != nil {
		fmt.Printf("Prev=%p | ptr=%p ele=%v | next=%p \n", cur.Prev, cur, cur.Ele, cur.Next)
		cur = cur.Prev //当前节点向前移动一位
	}
}

// GetHead
//
//	@Description: 获取头节点
//	@param n
//	@return head
func GetHead(n *Node) (head *Node) {
	current := n
	for current != nil {
		if current.Prev == nil { //当前节点的前驱节点为空，说明是头节点
			head = current
			break
		}
		//向前移动一位
		current = current.Prev
	}
	return head
}

// GetTail
//
//	@Description: 获取尾节点
//	@param n
//	@return tail
func GetTail(n *Node) (tail *Node) {
	current := n
	for current != nil {
		if current.Next == nil { //当前节点的后继节点为空，说明是尾节点
			tail = current
			break
		}
		//向后移动一位
		current = current.Next
	}
	return tail
}

// DeleteNode
//
//	@Description: 删除元素
//	@param n
//	@param e
func DeleteNode(n *Node, e interface{}) {
	var node *Node = nil
	if rand.Intn(2) == 1 {
		//从头开始查找
		node = GetNodeFromHeadToTail(n, e)
	} else {
		//从尾开始查找
		node = GetNodeFromTailToHead(n, e)
	}
	if node != nil { //查找到了
		if node.Prev != nil {
			node.Prev.Next = node.Next //节点的前驱节点不为空，则前驱的next -> 节点的后继节点
		}
		if node.Next != nil {
			node.Next.Prev = node.Prev //节点的后继节点不为空，则后继的prev -> 节点的前驱节点
		}
	}
}

// GetNodeFromHeadToTail
//
//	@Description:
//	@param n
//	@param e
//	@return node
func GetNodeFromHeadToTail(n *Node, e interface{}) (node *Node) {
	if n == nil {
		return nil
	}
	head := GetHead(n)
	current := head
	for current != nil {
		if current.Ele == e {
			return current
		}
		current = current.Next //向后移动一位
	}
	return nil
}

// GetNodeFromTailToHead
//
//	@Description: 从尾开始查找
//	@param n
//	@param e
//	@return node
func GetNodeFromTailToHead(n *Node, e interface{}) (node *Node) {
	if n == nil {
		return nil
	}
	tail := GetTail(n)
	current := tail
	for current != nil {
		if current.Ele == e {
			return current
		}
		current = current.Prev //向前移动一位
	}
	return nil
}
